//https://leetcode.cn/problems/total-cost-to-hire-k-workers/?envType=daily-question&envId=2024-05-01https://leetcode.cn/problems/total-cost-to-hire-k-workers/?envType=daily-question&envId=2024-05-01

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        priority_queue<int, vector<int>, greater<int>> left, right;
        int64_t n = costs.size(), i = 0, j = n - 1, ans = 0;
        for (; i < candidates && i <= j; i++, j--) {
            if (i == j) {
                left.push(costs[i++]);
                break;
            }
            left.push(costs[i]);
            right.push(costs[j]);
        }
        while (k --) {
            if (!left.empty() && !right.empty()) {
                if (left.top() <= right.top()) {
                    ans += left.top();
                    left.pop();
                    if(i <= j) left.push(costs[i++]);
                } else {
                    ans += right.top();
                    right.pop();
                    if(i <= j) right.push(costs[j--]);
                }
            } else {
                if (!left.empty()) {
                    ans += left.top();
                    left.pop();
                    if(i <= j) left.push(costs[i++]);
                } else {
                    ans += right.top();
                    right.pop();
                    if(i <= j) right.push(costs[j--]);
                }
            }
        }
        return ans;
    }
};